package airthmetic.exercise.linkedList;

public class _147_对链表进行插入排序 {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = head.next;
        ListNode last = head;
        ListNode temphead = dummyNode;
        while (pre != null) {
            if (last.val <= pre.val) {
                pre = pre.next;
                last = last.next;
                continue;
            }
            temphead = dummyNode;

            while (temphead.next.val <= pre.val) {
                temphead = temphead.next;
            }
            last.next = pre.next;
            pre.next = temphead.next;
            temphead.next = pre;
            pre = last.next;
        }

        return dummyNode.next;
    }
}
